8.14 Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that n is prime if and only if n divides (2n2). a. Give an example that satisfies the condition using an odd prime. b. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime (proving the if condition) c. Give an example of an odd n that is not prime and that does not satisfy the condition. You can do this with nonprime numbers up to a very large value. This misled the Chinese mathematicians into thinking that if the condition is true then n is prime. Unfortunately, the ancient Chinese never tried n = 341, which is non prime (341 = 11 x 31) and yet 341 divides 2 341 = 2 with out remainder. Demonstrate that 2 341 = 2 (mod 341) (disproving theonly if condition). Hint: It is not necessary to calculate 2 341; play around with the congruences instead. | |
| View Solution | |
| << Back | Next >> |